package com.javatest2;

import java.util.Arrays;

/**
 * @author LL
 * 给定一个数组a，和一个目标值k，我们假定一个集合是合法
 * 的，需要满足如下两个条件： 1、集合非空 2、设集合中的元
 * 素最小值为min，最大值为max，要求min+max<=k 现在，请
 * 问有多少个集合满足条件。输出满足的集合个数。 由于这个个
 * 数可能会很大，所以你只需要返回对1000000007取模的结
 * 果。
 * @create 2021-02-01 13:22
 */

/**
 * 对于长度为n，最小值为min，最大值为max，且min +
 * max <= k 的数组，他有 2 ^ (n - 1) 个符合要求且最小
 * 值为min的集合。对原数组进行排序，找出与a[0]相加
 * 不超过k的最大值a[j]。遍历a[0]到a[j]之间的数，对于每
 * 次遍历，寻找与该数相加最大但小于等于k另一个数，
 * 以这两个数之间的数作为子数组，将其对应的集合数加
 * 入结果中。
 */
public class Subject10 {
    /**
     * @param a: the array
     * @param k: the target
     * @return: the sum of the legal set
     */

    public static int theSumofLegalSet(final int[] a, final int k) {
        // Write your code here.
        final int[] tmp = new int[10001];
        final int mod = (int) 1e9 + 7;
        int i, j;
        int ans;
        Arrays.sort(a);
        tmp[0] = 1;
        for (i = 1; i <= 10000; i++) {
            tmp[i] = tmp[i - 1] * 2 % mod;
        }
        j = -1;
        for (i = 0; i < a.length; i++)
            if (a[i] + a[0] <= k) j = i;
            else break;
        if (j == -1) return 0;
        ans = tmp[j];
        for (i = 1; i < a.length; i++) {
            while (a[i] + a[j] > k && j > i) j--;
            if (a[i] + a[j] > k) return ans;
            ans = (ans + tmp[(j - i)]) % mod;
        }
        return ans;
    }

    public static void main(final String[] args) {
        final int[] a = {1, 5, 2, 3, 7, 8, 9, 4};
        final int i = theSumofLegalSet(a, 9);
        System.out.println(i);
    }

}
